Max-product Algorithm

释义 Definition

最大积算法：一种在因子图/马尔可夫随机场等图模型上进行消息传递（message passing）的推断方法，用于寻找最可能解释（MAP）的变量赋值。它常被视为 sum-product algorithm（和-积算法）在“取最大值”意义下的对应版本（在对数域中常写成 max-sum）。

例句 Examples

We used the max-product algorithm to find the most likely labels.
我们用最大积算法来找到最可能的标签。

On a factor graph with loops, the max-product algorithm can give a good approximate MAP solution, though it is not always guaranteed to be optimal.
在带有环的因子图上，最大积算法往往能给出不错的近似 MAP 解，但并不总能保证全局最优。

发音 Pronunciation (IPA)

/ˌmæks ˈprɒdʌkt ˈælɡəˌrɪðəm/

词源 Etymology

“max-product”由 max（取最大值）与 product（乘积）组合而来，指在概率模型中把多个因子的乘积作为目标，并通过“取最大”来寻找最可能的配置；“algorithm”来自希腊-拉丁学术传统，经由中世纪对数学家 al-Khwārizmī（花剌子密）姓名的拉丁化形式演变而来，泛指“算法/步骤体系”。

相关词 Related Words

• Belief Propagation
• Sum-Product Algorithm
• Max-Sum Algorithm
• MAP Inference
• Factor Graph
• Message Passing
• Viterbi Algorithm
• Dynamic Programming

文献与作品 Literary / Notable Works

• Kschischang, Frey, Loeliger (2001), Factor Graphs and the Sum-Product Algorithm（讨论 sum-product，并常对照介绍 max-product / max-sum 的 MAP 版本）
• Judea Pearl (1988), Probabilistic Reasoning in Intelligent Systems（图模型推断与消息传递思想的经典来源之一，相关内容常引出 max-product 形式）
• Christopher M. Bishop (2006), Pattern Recognition and Machine Learning（概率图模型章节中涉及 MAP 推断与消息传递方法，常出现 max-product/max-sum 表述）